package sword;

/**
 * @author caifangyi
 * @date 2022/7/18
 */

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 滑动窗口的平均值
 *
 * 给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。
 *
 * 实现 MovingAverage 类：
 *
 * MovingAverage(int size) 用窗口大小 size 初始化对象。
 * double next(int val)成员函数 next每次调用的时候都会往滑动窗口增加一个整数，请计算并返回数据流中最后 size 个值的移动平均值，即滑动窗口里所有数字的平均值。
 * 
 *
 * 示例：
 *
 * 输入：
 * inputs = ["MovingAverage", "next", "next", "next", "next"]
 * inputs = [[3], [1], [10], [3], [5]]
 * 输出：
 * [null, 1.0, 5.5, 4.66667, 6.0]
 *
 * 解释：
 * MovingAverage movingAverage = new MovingAverage(3);
 * movingAverage.next(1); // 返回 1.0 = 1 / 1
 * movingAverage.next(10); // 返回 5.5 = (1 + 10) / 2
 * movingAverage.next(3); // 返回 4.66667 = (1 + 10 + 3) / 3
 * movingAverage.next(5); // 返回 6.0 = (10 + 3 + 5) / 3
 * 
 *
 * 提示：
 *
 * 1 <= size <= 1000
 * -105 <= val <= 105
 * 最多调用 next 方法 104 次
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/qIsx9U
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Sword0041 {

    public static void main(String[] args) {
        MovingAverage movingAverage = new MovingAverage(3);
        double next = movingAverage.next(1);// 返回 1.0 = 1 / 1
        double next1 = movingAverage.next(10);// 返回 5.5 = (1 + 10) / 2
        double next2 = movingAverage.next(3);// 返回 4.66667 = (1 + 10 + 3) / 3
        double next3 = movingAverage.next(5);// 返回 6.0 = (10 + 3 + 5) / 3

        System.out.println(next +","+next1+","+next2+","+next3);
    }

    static class MovingAverage {

        int size;
        Deque<Double> deque;
        double sum = 0;

        /** Initialize your data structure here. */
        public MovingAverage(int size) {
            this.deque = new LinkedList<>();
            this.size = size;
        }

        public double next(int val) {
            boolean isFull = deque.size() >= size;
            if(isFull){
                sum -= deque.pop();
            }
            deque.add((double) val);
            sum += val;
            return sum/deque.size();
        }
    }
}
